/*
 * @lc app=leetcode.cn id=739 lang=cpp
 *
 * [739] 每日温度
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // vector<int> res;
        // int total = temperatures.size();
        // for (int i=0;i<total-1;++i){
        //     int days = 0;
        //     int temperatureNow = temperatures[i];
        //     bool higherExist = false;

        //     if (i>0 and temperatureNow == temperatures[i-1]){
        //         int last = res.back();
        //         if (last == 0){
        //             res.emplace_back(0);
        //         }else{
        //             res.emplace_back(last-1);
        //         }
        //         continue;
        //     }

        //     for (int j=i;j<total-1;++j){
        //         ++days;
        //         if (temperatures[j+1] > temperatureNow){
        //             res.emplace_back(days);
        //             higherExist = true;
        //             break;
        //         }
        //     }

        //     if (!higherExist){
        //         res.emplace_back(0);
        //     }
        // }
        // res.emplace_back(0);
        // return res;

        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> indices;
        for (int i = 0; i < n; ++i) {
            while (!indices.empty()) {
            int pre_index = indices.top();
            if (temperatures[i] <= temperatures[pre_index]) {
                break;
            }
            indices.pop();
            ans[pre_index] = i - pre_index;
            }
        indices.push(i);
        }
        return ans;
    }
};
// @lc code=end

